package slidingwindow;

import java.util.ArrayList;
import java.util.List;

//找到字符串中所有字⺟异位词
public class FindAnagrams {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        System.out.println(findAnagrams(s, p));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (char ch : pp) hash1[ch - 'a']++;
        int m = p.length();
        for (int right = 0, left = 0, count = 0; right < s.length(); right++) {
            char in = ss[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
            if (right - left + 1 > m) {
                char out = ss[left++];
//                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
                if (hash2[out - 'a'] <= hash1[out - 'a']) {
                    count--;
                }
                hash2[out - 'a']--;
            }
            if (count == m) ret.add(left);
        }
        return ret;
    }


//    public static List<Integer> findAnagrams(String s, String p) {
//        List<Integer> ret = new ArrayList<Integer>();
//        char[] ss = s.toCharArray();
//        char[] pp = p.toCharArray();
//        int hash1[] = new int[26];//统计字符串p中每一个字符出现的个数
//        for (char ch : pp) {
//        hash1[ch-'a']++;
//        }
//        int hash2[] = new int[26];//统计窗口中每一个字符出现的个数
//        int m = p.length();
//        for (int right = 0, left = 0,count = 0; right < s.length(); right++) {
//            char in = ss[right];
//            if(++hash2[in-'a'] <= hash1[in-'a']) {
//                count++;
//            }
//            if(right - left + 1 > m) {
//                char out = ss[left++];
//                System.out.println("1: "+hash2[out-'a']);
//                if(hash2[out-'a']-- <= hash1[out-'a']) {  //先比较再--
//
//                    count--;
//                }
//            }
//            if(count == m) {
//                ret.add(left);
//            }
//        }
//        return ret;
//    }
}
